# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        list_p, list_q = [], []
        if p:
            self.search(p, list_p)
        if q:
            self.search(q, list_q)
        print(list_q, list_p)
        return list_p == list_q

    def search(self, root: TreeNode, list_in):
        if not root.left and not root.right:
            list_in.append(root.val)
            return
        if root.left:
            self.search(root.left, list_in)
        else:
            list_in.append(None)
        list_in.append(root.val)
        if root.right:
            self.search(root.right, list_in)
        else:
            list_in.append(None)


a = TreeNode(1)
b = TreeNode(1)
c = TreeNode(1)
d = TreeNode(1)
a.left = b
c.right = d
d = Solution()
d.isSameTree(a, c)